package org.laizili.solution.leetcode;

import java.util.*;

/**
 * <a href="https://leetcode.cn/problems/pacific-atlantic-water-flow/">417. 太平洋大西洋水流问题</a>
 * <p>
 * tags: 图的遍历; (多源) BFS; DFS; 并查集
 * <p>
 * notes: 逆向思维（顺流而下，也可逆流而上）
 * <a href="https://leetcode.cn/problems/pacific-atlantic-water-flow/solution/by-ac_oier-do7d/">优质题解</a>
 */
public class Problem417 {
    // 我的题解： BFS爆搜
    private static class Solution {
        public List<List<Integer>> pacificAtlantic(int[][] heights) {
            int m = heights.length;
            int n = heights[0].length;
            List<List<Integer>> list = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (isTrue(heights, m, n, i, j)) {
                        list.add(Arrays.asList(i, j));
                    }
                }
            }
            return list;
        }

        private static final int[][] direction = new int[][]{{0, 1, 0, -1}, {1, 0, -1, 0}}; // (顺时针)右 下 左 上  
        private static final int DL = 4;

        public boolean isTrue(int[][] heights, int m, int n, int sx, int sy) {
            Deque<int[]> queue = new ArrayDeque<>();
            queue.add(new int[]{sx, sy});
            boolean leftOrUpperBounding = false;  // 左或上边界
            boolean rightOrLowerBounding = false; // 右或下边界
            boolean[][] traversed = new boolean[m][n];
            traversed[sx][sy] = true;
            while (!queue.isEmpty() && (!leftOrUpperBounding || !rightOrLowerBounding) /*剪枝: 满足条件后就不搜了*/) {
                int[] xy = queue.pop();
                for (int i = 0; i < DL; i++) {
                    int nx = xy[0] + direction[0][i];
                    int ny = xy[1] + direction[1][i];

                    if (nx < 0) {
                        if (ny >= n - 1) {
                            rightOrLowerBounding = true;
                        }
                        leftOrUpperBounding = true;
                    } else if (nx >= m) {
                        if (ny <= 0) {
                            leftOrUpperBounding = true;
                        }
                        rightOrLowerBounding = true;
                    } else if (ny < 0) {
                        if (nx >= m - 1) {
                            rightOrLowerBounding = true;
                        }
                        leftOrUpperBounding = true;
                    } else if (ny >= n) {
                        if (nx <= 0) {
                            leftOrUpperBounding = true;
                        }
                        rightOrLowerBounding = true;
                    } else {
//                        nx >= 0 && nx < m && ny >=0 && ny<n
                        if (heights[nx][ny] <= heights[xy[0]][xy[1]] && !traversed[nx][ny]) {
                            queue.add(new int[]{nx, ny});
                            traversed[nx][ny] = true;
                        }
                    }
                }
            }
            return leftOrUpperBounding && rightOrLowerBounding;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().pacificAtlantic(new int[][]{{2, 1}, {1, 2}}));
        System.out.println(new Solution().pacificAtlantic(new int[][]{
                {1, 2, 2, 3, 5},
                {3, 2, 3, 4, 4},
                {2, 4, 5, 3, 1},
                {6, 7, 1, 4, 5},
                {5, 1, 1, 2, 4}
        }));
        System.out.println(new Solution().pacificAtlantic(new int[][]{{2, 2, 2}, {2, 1, 2,}, {2, 2, 2}}));
    }

}
